package bite;

/**
 * Creared with IntelliJ IDEA.
 * Description:【数组中出现次数超过一半的数字】
 * 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
 * User:yxd
 * Date:2022-03-25
 * Time:16:26
 */
import java.util.*;
public class Day3_2 {
    public int MoreThanHalfNum_Solution1(int [] array) {//排序找中间值
        if(array.length == 0)return 0;
        if(array.length == 1)return array[0];
        Arrays.sort(array);//但是其实使用这个排序底层在一定范围内使用归并,一定范围使用其他快排,归并...这效率还是挺慢的最少(n*log(n)),因此推荐使用下面的方法
        int a = array[array.length / 2];
        int count = 0;
        for(int i = 0;i < array.length;i ++){
            if(array[i] == a){
                count ++;
            }
        }
        if(count > array.length / 2){
            return a;
        }else{
            return 0;
        }
    }
    public int MoreThanHalfNum_Solution(int [] array) {//抵消法
        int result = array[0];//赋初值
        int times = 1;//result出现的次数
        for (int i = 1; i < array.length; i++) {
            if(times != 0){
                if(result != array[i]){
                    times --;//抵消掉不相同的
                }else{
                    times ++;//出现相同的就给次数加一
                }
            }else{//此时这个数已经被消除完了,需要重新赋值
                result = array[i];
                times = 1;

            }
        }
        //走完如果存在众数那么result里面存放的一定是
        int count = 0;
        for(int i = 0;i < array.length;i ++){
            if(array[i] == result){
                count ++;
            }
        }
        if(count > array.length / 2){
            return result;
        }else{
            return 0;
        }

    }
}